package easy;

public class leetcode69_NumberSqrt {
    public static int mySqrt(int x) {
        // 二分查找法
        // 首先定义左右指针l，f，ans为返回值的初始化
        int l = 0, r = x, ans = -1;
        // 对于左闭右闭区间循环查找
        while (l <= r) {
            // 查找中间值
            int mid = l + (r - l) / 2;
            // 对于中间值进行平方并与x进行比较
            // 如果mid*mid 小于等于 x 则将左指针进行右移
            // 如果mid*mid 大于x 则将右指针进行左移
            // 当左指针大于右指针则跳出循环
            if ((long) mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;

    }

    public static void main(String[] args) {
        System.out.println(mySqrt(8));
    }
}
